package com.algorithm.dp;

import java.util.Stack;

import static com.google.common.primitives.Ints.max;


public class MaxHistogram {
    public static void main(String[] args) {
        int[] height = {1,2,3,1,3,6};
        int answer = getAnswer(height);
        System.out.println(answer);
    }
    /**
     n：意义如题
     height：高度数组，height[i]表示第i列的高度（下标从1开始），数组大小为n+2，其中height[0]和height[n+1]都为0
     返回值：题目所求答案，即最大面积

     使用单调栈解答.单调栈是使用栈结构保存单调序列下标的结构,
     */
    public static int getAnswer(int[] source) {
        int[] height = new int[source.length+2];
        System.arraycopy(source,0,height,1,source.length);

        int ans = 0;
        Stack<Integer> myStack = new Stack<>();
        /* push(0) 是为了能把第一个元素入栈 */
        myStack.push(0);
        /* 从N+1开始是为了把最后一个元素和第一个元素也弹出来 */
        for (int i = 1; i <= height.length - 1; ++i) {
            while ((height[myStack.peek()] > height[i])) {
                int nowHeight = height[myStack.peek()];
                myStack.pop();
                int nowWidth = i - myStack.peek() - 1;
                ans = max(ans, nowHeight * nowWidth);
            }
            myStack.push(i);
        }
        return ans;
    }


}
